"""
Problem 35: https://projecteuler.net/problem=35

The number 197 is called a circular prime because all rotations of the digits:
197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73,
79, and 97.
How many circular primes are there below one million?

"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/12
'''


def isPrime(n: int) -> bool:
    '''
    >>> assert all([isPrime(n) for n in [2,3,5,7,11,13]])
    >>> assert not any([isPrime(n) for n in [4,6,8,9,12,25]])
    '''
    if n < 2:
        return False
    if n == 2:
        return True

    n_sqrt = int(n**0.5)
    if n_sqrt**2 == n:
        return False

    for i in range(2, n_sqrt+1):
        if n % i == 0:
            return False

    return True


def isCircularPrime(n: int) -> bool:
    ns = str(n)
    if n > 10 and any(['2' in ns, '4' in ns, '5' in ns, '6' in ns, '8' in ns, '0' in ns]):
        return False

    if not isPrime(n):
        return False

    d = len(str(n))
    for _ in range(d-1):
        n = (n % 10)*(10**(d-1)) + (n//10)
        if not isPrime(n):
            return False

    return True


def solution(limit: int = 1000000) -> int:
    '''
    How many circular primes are there below one million?

    >>> assert solution(100) == 13
    '''
    if limit < 2:
        return 0
    count = 1  # prime 2
    for i in range(3, limit, 2):
        if isCircularPrime(i):
            # print('CircularPrime: ', i)
            count += 1

    return count


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 55
